This is my primary focus. Here are some helpful conceptual graph links :

• Definition of CG's (Sowa)
• The Peirce Project
• CGTools Home Page
• Conceptual graph tools available from CMU AI Repository
• Axiomatization Of a Conceptual Graph Formalism For Information Retrieval (abstract)
• Conceptual Graph Research at LIRMM
• Conceptual Graph Editor Project Description
• Conceptual Graphs and Manufacturing Processes
• Exploiting Conceptual Graphs for Knowledge Reuse in Design
• Knowledge Modeling Using Conceptual Graphs (Call for papers)
• Existential Graph Lecture Notes
• Peirce-L Archive

Last Update 11 January, 1998

Introduction to Conceptual Graphs
Lecture Notes in Progress

Conceptual graphs (CG) are a graph knowledge representation system invented byJohn Sowa which integrate a concept hierarchy with the logic system of Peirce's existential graphs. Conceptual graphs are as general as predicate logic and have a standard mapping to natural language. The standard reference is Sowa's ConceptualStructures: Information Processing in Mind and Machine.

Conceptual graphs are represented as finite, bipartite, possibly connected graphs. The two kinds of nodes of the graphs are concepts and conceptual relations which are connected by untyped arcs. Each conceptual graph forms a proposition. The above conceptual graph in first order predicate logic is :
Conceptual graphs have the same expressive power of first order logic, frames, scriptsand incorporate modal logic.

Concept Hierarchy

A pre-existent type hierarchy of concept types is assumed to exist for each conceptualgraph system. A relation < is defined over the set of concepts to showconcept types that are subsumed in others. For example, if PHYSICAL-OBJECT, ANIMAL, MAMMAL, and CAT wereconcept types, the relations
CAT < MAMMAL < ANIMAL < PHYSICAL-OBJECT
would exist.

A Partial Type Hierarchy

The above concept types could have been extracted from the above type hierarchy.There are two special concept types: T, the supertype of all types and the absurdtype (not shown) which is the subtype of all types and is designated by an invertedT.
The minimal common supertype, s U t, is a type label that is the supertype of boths and t.The maximal common subtype, , is a type label that is the subtype of both sand t and is a supertype of any other subtype.The conformity relation, t::i, ensures that an individual i is type conformant with thetype label t.

Concepts
A concept is an instantiation of a concept type. A concept by itself is a conceptual graphand conceptual graphs may be nested within concepts. However, two or more unnestedconcepts in the same conceptual graph must be connected using links to a relation.
A concept can be written in graphical notation as:
or in linear notation as: [Concept].

Each concept has a referent field used to identify the concept specifically or to generalizethe concept, to perform quantification, to provide a query mechanism, etc.

[Cat] The Cat concept in general
[Cat: *x] same as above
[Cat: #920229] a specific cat
[Cat: Bat] same as above but by name (the name of one of my cats)
[Employee: {*} ?] a querry
[Female: #] a female mentioned in a specific context
[Cat: {*}@2] two cats

Conceptual Relations
For any given conceptual graph system there is a predefined catalog of conceptualrelations which defines how concepts may be linked with relations. The semanticsof n concepts linked to a relation would be expressed in predicate form as:Relation(concept1, concept2, ..., conceptN). The majority of conceptual relationswill have two concepts because we ordinarily think this way. With this class ofconceptual relations, the semantics are usually expressed as concept1 Relationconcept2.



Cannonical Graphs
Cannonical graphs repesent real or possible situations in the world. Cannonical graphsare formed through perception, insight, or are derived from other cannonical graphsusing formation rules. Cannonical graphs are a restriction ov what is possible to modelusing conceptual graphs since their intent is to weed out absurdities or nonsenseformulations.

A cannonical graph, w ,may be derived from other cannonical graphs , u,v, whereu and v may be the same graph by formation rules: copy, restruct,join, and simplify. The formation rules formone of two independent proof mechanisms.

• copy: w is an exact copy of u.
  
  
• restrict: For any concept c in u, type(c) may be replaced by asubtype. If c is generic, its referent may be changed to an individual marker. referent(c)must conform to type(c) before and after the hange.
• join: If a concept c in u is identical to a concept d in v, thenlet w be the graph obtained by deleting d and linking to c all arcs of conceptual relationsthat have been linked to d.
• simplify: If conceptual relations r and s in the graph u areduplicates, then delete one of them, including all its arcs.

A maximal join is the join of two graphs followed by a sequence ofrestrictions, internal joins (joins on other concepts), and simplifications until no futheroperation is possible. A maximal join acts as unification for conceptual graphs.

Abstractions
New concept types and relations may be defined using abstractions. An abstraction is aconceptual graph with generic concepts and a formal parameter list.
Quick-Eater = (lambda x) [Person: *x]<-(Agent)<-[Eat]->(Manner)->[Fast].
type Positive(x) is [Number: *x]->(<)->[Number: 0].
Country-of-Residence =
(lambda x,y) [Person: *x]->(State)->[Live]->(In)->[Country: *y].
Sowa originally made a distinction between an abstraction and a new type label definitionbut this distinction seems to have been dropped.

Schemata and Prototypes
Schemata incorporate domain-specific knowledge about typical objects found in thereal world. Schemata define what is plausible about the world. Schemata are similarto type definitions except that there may be only one type definition but many schemata.

A prototype is a typical instance of an object. A prototype specializes concepts in one ormore schemata. The defaults are true of a typical case but may not be true of a specificinstance. A prototype can be derived from schemata by maximal joins and then assigningreferents to some of the generic concepts in the result.

Inference RulesThe inference rules discussed here are the second conceptual graph proof mechanism .Whereas the cannonical graph formation rules use information found in the typehierarchy, the inference rules operate on a conceptual graph directly.

The inference rules are taken directly from the Alpha and Beta rules ofPierce's existential graphs.